package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: ½£Ö¸ Offer 62. Ô²È¦ÖÐ×îºóÊ£ÏÂµÄÊý×Ö
 * 0,1,¡¤¡¤¡¤,n-1Õân¸öÊý×ÖÅÅ³ÉÒ»¸öÔ²È¦£¬´ÓÊý×Ö0¿ªÊ¼£¬
 * Ã¿´Î´ÓÕâ¸öÔ²È¦ÀïÉ¾³ýµÚm¸öÊý×Ö£¨É¾³ýºó´ÓÏÂÒ»¸öÊý×Ö¿ªÊ¼¼ÆÊý£©¡£Çó³öÕâ¸öÔ²È¦ÀïÊ£ÏÂµÄ×îºóÒ»¸öÊý×Ö¡£
 * <p>
 * ÀýÈç£¬0¡¢1¡¢2¡¢3¡¢4Õâ5¸öÊý×Ö×é³ÉÒ»¸öÔ²È¦£¬´ÓÊý×Ö0¿ªÊ¼Ã¿´ÎÉ¾³ýµÚ3¸öÊý×Ö£¬ÔòÉ¾³ýµÄÇ°4¸öÊý×ÖÒÀ´ÎÊÇ2¡¢0¡¢4¡¢1£¬Òò´Ë×îºóÊ£ÏÂµÄÊý×ÖÊÇ3¡£
 * <p>
 * Ê¾Àý 1£º
 * <p>
 * ÊäÈë: n = 5, m = 3
 * Êä³ö:3
 * <p>
 * À´Ô´£ºÁ¦¿Û£¨LeetCode£©
 * Á´½Ó£ºhttps://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
 * Öø×÷È¨¹éÁì¿ÛÍøÂçËùÓÐ¡£ÉÌÒµ×ªÔØÇëÁªÏµ¹Ù·½ÊÚÈ¨£¬·ÇÉÌÒµ×ªÔØÇë×¢Ã÷³ö´¦¡£
 *
 * @Author: future
 * @Date:2022/5/14:16:15
 */
public class Solution_62_lastRemaining {

    public static void main(String[] args) {
        //int n = 10, m = 17;
        int n = 5, m = 3;
        //int n = 5, m = 2;
        System.out.println(lastRemaining(n, m));
    }

    public static int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int M = m;
        while (n > 1) {
            // ÒªÒÆ³ýµÄÏÂ±ê
            int i = (M % n);
            System.out.println("ÒÆ³ýµÄÖµ£º" + list.get(i == 0 ? n - 1 : i - 1));
            list.remove(i == 0 ? n - 1 : i - 1);
            // ÐèÒªadd¸ö²¹ÆëÊý×é
            int fillUp = n - i;
            M = m < fillUp ? fillUp : (m - fillUp == 0 ? n : m - fillUp);
            n--;
        }
        return list.get(0);
    }
}
